public class code1 {
    //回文子串
    public int countSubstrings(String s) {
        int n = s.length();
        boolean[][] dp = new boolean[n][n];

        //初始化：i+1<j这样就已经处理了越界情况

        //统计返回值:边填表边统计
        int ret = 0;

        for(int i=n-1;i>=0;i--) {
            for(int j=i;j<=n-1;j++) {
                //(1)本来就为false无需考虑
                //(2)
                if(s.charAt(i)==s.charAt(j)) {
                    if(i==j||i+1==j) dp[i][j]=true;//这里就包含了dp[n][x]
                    else dp[i][j] = dp[i+1][j-1];
                }
                if(dp[i][j]==true) ret++;
            }
        }

        return ret;
    }
}
